﻿#pragma once

#include <utility>
#include <vector>
#include <cassert>
#include <string>

namespace close
{

	enum State
	{
		EMPTY,
		EXIST,
		DELETE
	};

	template <class key, class value>
	struct HashData
	{
		std::pair<key, value> _kv;
		State _state = EMPTY;
	};

	template <class key, class value>
	class HashTable
	{
		typedef HashData<key, value> Data;
		typedef HashTable<key, value> Self;

	public:

		HashTable()
		{
			_table.resize(10);
		}

		bool insert(const std::pair<key, value>& kv)
		{
			if (find(kv.first) != nullptr)
			{
				return false;
			}
			//负载因子大于0.7
			if (__valid_elem * 10 / _table.size() >= 7)
			{
				Self newHashTable;
				newHashTable._table.resize(2 * _table.size());
				for (auto& e : _table)
				{
					if (e._state == EXIST)
					{
						newHashTable.insert(e._kv);
					}
				}
				_table.swap(newHashTable._table);
			}
			size_t hashi = kv.first % _table.size();
			while (_table[hashi]._state == EXIST)
			{
				++hashi;
				hashi %= _table.size();
			}
			_table[hashi]._kv = kv;
			_table[hashi]._state = EXIST;
			++__valid_elem;

			return true;
		}

		Data* find(const key& k)
		{
			size_t hashi = k % _table.size();

			while (_table[hashi]._state != EMPTY)
			{
				if (_table[hashi]._state == EXIST
					&& _table[hashi]._kv.first == k)
				{
					return &_table[hashi];
				}
				++hashi;
				hashi %= _table.size();
			}
			return nullptr;
		}

		bool erase(const key& k)
		{
			Data* res = find(k);
			if (__valid_elem != 0 && res == nullptr)
			{
				return false;
			}
			res->_state = DELETE;
			--__valid_elem;
			return true;
		}

	private:
		std::vector<Data> _table;
		size_t __valid_elem = 0;
	};



}

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct HashFunc<std::string>
{
	size_t operator()(const std::string& key)
	{
		size_t hash = 0;
		for (size_t i = 0; i<key.size(); ++i)
		{
			hash += key[i];
			hash *= 131;
		}
		return hash;
	}
};

namespace bucket
{
	template<class K, class V>
	struct HashNode
	{
		HashNode<K,V>* _next;
		std::pair<K, V> _kv;

		HashNode(const std::pair<K, V>& kv)
			: _next(nullptr)
			, _kv(kv)
		{}
	};

	template<class K, class V, class Hash, class KeyOfV>
	struct HashIterator
	{
		typedef HashNode<K, V> Node;
		typedef HashIterator<K, V, Hash, KeyOfV> Self;
		typedef HashTable<K, V, Hash> Table;


		Node* _node;
		Table* __hash_table;

		HashIterator(Node* node, Table* table)
			: _noed(node)
			, __hash_table(table)
		{}

		V& operator*()
		{
			return _node->_kv.second;
		}

	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:

		HashTable()
			: _size(0)
		{
			_table.resize(10);
		}

		bool insert(const std::pair<K, V>& kv)
		{
			if (find(kv.first) != nullptr)
			{
				return false;
			}

			if (_table.size() == _size)
			{
				std::vector<Node*> newtable;
				newtable.resize(2 * _size, nullptr);

				for (auto node : _table)
				{
					Node* cur = node;
					while (cur)
					{
						Node* next = cur->_next;
						size_t hashi = Hash()(cur->_kv.first) % newtable.size();
						cur->_next = newtable[hashi];
						newtable[hashi] = cur;
						cur = next;
					}
					node = nullptr;
				}

				_table.swap(newtable);
			}


			size_t hashi = Hash()(kv.first) % _table.size();
			Node* newnode = new Node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			++_size;

			return true;
		}

		bool erase(const K& key)
		{
			size_t hashi = Hash()(key) % _table.size();
			Node* prev = nullptr;
			Node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (_table[hashi] == cur)
					{
						_table[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					--_size;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}

		Node* find(const K& k)
		{
			size_t hashi = Hash()(k) % _table.size();
			Node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_kv.first == k)
					return cur;
				else
					cur = cur->_next;
			}
			return nullptr;
		}

	private:
		std::vector<Node*> _table;
		size_t _size = 0;
	};

}